package lkx.demo.test4;

/**
 * 排序算法的衡量标准：① 时间复杂度（最重要） ② 空间复杂度 ③ 稳定性
 * Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n<sup>2</sup>)＜Ο(n<sup>3</sup>)＜…＜Ο(2<sup>n</sup>)＜Ο(n!)<O(n<sup>n</sup>)
 *
 * 排序的分类：内部排序（内存中排序）；外部排序（外部存储设备+内存）
 *
 * 内部排序的具体算法：10种。
 *
 * 我们需要关注的几个排序算法：
 * > 冒泡排序：最简单，需要大家会手写。时间复杂度：O(n^2)
 * > 快速排序：最快的，开发中默认选择的排序方式；掌握快速排序的实现思路；时间复杂度：O(nlogn)
 *
 *
 *
 *
 *
 * @author kunxianli
 * @date 2024/02/01 11:28
 **/
public class TestArraySort2 {

    // 快速排序：最快的，开发中默认选择的排序方式；掌握快速排序的实现思路；时间复杂度：O(nlogn)

    /**
     * 1. 从数列中挑出一个元素，称为"基准"（pivot），
     * 2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
     * 在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
     * 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
     * 4. 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然
     * 一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至
     * 少会把一个元素摆到它最后的位置去。
     *
     *  这里用到递归的思想
     *
     */

    public static void main(String[] args) {
        int[] data = {9, -16, 30, 23, -30, -49, 25, 21, 30};
        System.out.println("排序之前：");
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+" ");
        }

        quickSort(data);//调用实现快排的方法

        System.out.println("\n排序之后：");
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+" ");
        }
    }

    public static void quickSort(int[] data) {
        subSort(data, 0, data.length - 1);
    }

    private static void subSort(int[] data, int start, int end) {
        if (start < end) {
            int base = data[start];
            int low = start;
            int high = end + 1;
            while (true) {
                while (low < end && data[++low] - base <= 0)
                    ;
                while (high > start && data[--high] - base >= 0)
                    ;
                if (low < high) {
                    //交换data数组[low]与[high]位置的元素
                    swap(data, low, high);
                } else {
                    break;
                }
            }
            //交换data数组[start]与[high]位置的元素
            swap(data, start, high);

            //经过代码[start, high)部分的元素 比[high, end]都小

            //通过递归调用，对data数组[start, high-1]部分的元素重复刚才的过程
            subSort(data, start, high - 1);
            //通过递归调用，对data数组[high+1,end]部分的元素重复刚才的过程
            subSort(data, high + 1, end);
        }
    }

    private static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
